UVa/11590 - Prefix lookup/asmaa.cpp

   1 struct trie_node {
   2
   3   // how many nodes are beneath this one?
   4   int count;
   5
   6   // array of pointers to children
   7   trie_node *child_list[ALPH_SIZE];
   8
   9   // initializer...
  10   trie_node();
  11 };
  12
  13 trie_node::trie_node() {
  14
  15   // there is nothing below us...
  16   count = 0;
  17
  18   // all child pointers start out pointing nowhere...
  19   for(int index = 0; index < ALPHABET_SIZE; index++)
  20     child_list[index] = NULL;
  21 }
  22
  23
  24
  25 class Trie {
  26
  27 public:
  28
  29   // methods
  30
  31   Trie(int level, int chars);        // create it
  32   ~Trie();                           // destroy trie nodes
  33   int node_count;                    // the number of nodes in whole trie
  34   void AddToTrie(const string \&s);   // add string to trie
  35
  36 private:
  37
  38   // methods
  39
  40   void recursive_delete (trie_node * t);     // recursive delete helper function
  41
  42
  43
  44   // data
  45
  46   int node_count;                      // number of nodes in the trie
  47   trie_node * Root;                  // the root of the trie
  48 };
  49
  50
  51
  52
  53 Trie::Trie() {
  54   node_count = 0;
  55   Root(new trie_node);
  56 }
  57
  58
  59 Trie::~Trie() {
  60
  61   // delete whole trie
  62   recursive_delete(myRoot);
  63 }
  64
  65
  66 void Trie::recursive_delete(trie_node * t) {
  67   int index;
  68
  69   if (t != NULL) {
  70
  71     // delete all children
  72     for(index = 0; index < ALPHABET_SIZE; index++)
  73       recursive_delete(t->child_list[index]);
  74
  75     // delete self
  76     delete t;
  77   }
  78 }
  79
  80
  81
  82
  83 int Trie::node_count() {
  84
  85   return (node_count);
  86
  87 }
  88
  89
  90
  91 void Trie::AddToTrie(const string \&s) {
  92   int lcv, index;
  93
  94   trie_node *t = Root;
  95
  96   // there is one more string stored somewhere under the root...
  97   t->count++;
  98
  99
 100   // loop over the length of the string to add and traverse the trie...
 101   for(lcv=0; lcv < s.length(); lcv++) {
 102
 103     index = s[lcv]; // the character in s we are processing...
 104
 105     // is there a child node for this character?
 106     if (t->child_list[index] == NULL) {
 107
 108       // if not, make one!
 109       t->child_list[index] = new trie_node;
 110       node_count++;
 111     }
 112
 113     // there is another string under this node...
 114     t->child_list[index]->count++;
 115
 116     // move to it this node... and loop
 117     t = t->child_list[index];
 118   }
 119 }
 120
 121 int N, M;
 122
 123
 124 int main(){
 125   while (cin >> N >> M && (N || M)){
 126     Trie t;
 127     unsigned long long i;
 128     string str;
 129     for(i=0; i<N; i++)
 130       {
 131         cin>>str;
 132         str = str.substr(0, str.size() - 1);        //to remove the *
 133         t.AddToTrie(str);
 134       }
 135     cin>>N;
 136     for(i=0; i<N; i++)
 137       {
 138         trie_node *r = t.Root;                     //I must keep the root of the Trie because I will change it later.
 139         cin>>str;
 140         str = str.substr(0, str.size() - 1);
 141         unsigned long long  j = 0;
 142         for(j=0; j<str.size(); j++)
 143           {
 144             t.Root = t.Root->child_list[str[j] - '0'];
 145           }
 146         unsigned long long  res = t.Find(str, 1);
 147         cout<<res<<endl;
 148         t.Root = r;                              //go back to the original root.
 149       }
 150     cout<<endl;
 151   }
 152   return 0;
 153 }